package util;

import model.Block;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 解决平均分配算法
 *
 * @author gubengang
 * @create 2021-10-10 20:48
 */
public class AverageDivideUtil {
    private AverageDivideUtil(){
    }

    public static double costTime(List<List<Block>> list, double speed){
        return list.stream().map(key->key.stream().map(Block::getSize)
                .mapToLong(Integer::longValue).sum()/(speed*1024*1024))
                .max(Double::compareTo).get();
    }

    public static List<List<Block>> average(List<Block> lengthList, int m){
        List<List<Block>> resultList = new ArrayList<>();
        if (lengthList.size() < m) {
            buildResultList(resultList, lengthList);
        } else {
            int[] pointArr = findSplitPoint(lengthList, m);
            buildResultList(resultList, lengthList, pointArr);
        }

        return resultList;
    }

    static void buildResultList(List<List<Block>> resultList, List<Block> dataList) {
        for (int i = 0; i < dataList.size(); i++) {
            List<Block> list = new ArrayList<>();
            list.add(dataList.get(i));
            resultList.add(list);
        }
    }

    static void buildResultList(List<List<Block>> resultList, List<Block> dataList, int[] resultArr) {
        if (resultList == null || dataList == null || resultArr == null) {
            return;
        }
        int j = 0;
        int maxJ = 0;
        for (int i = 0; i <= resultArr.length; i++) {
            if (i == resultArr.length) {
                maxJ = dataList.size();
            } else {
                maxJ = resultArr[i];
            }
            List<Block> list = new ArrayList<>();
            for (; j < maxJ; j++) {
                list.add(dataList.get(j));
            }
            resultList.add(list);
        }
    }


    private static int[] findSplitPoint(List<Block> lengthList, int m) {
        int totalNum = 0;
        for (int i = 0; i < lengthList.size(); i++) {
            totalNum += lengthList.get(i).getSize();
        }
        //平均值
        double average = (double) totalNum / (double) m;
        System.out.println("average=" + average);
        int groupNum = 0;
        int[] pointArr = new int[m - 1];
        int pointArrIndex = 0;
        double minDiffSum = -1;
        int i = 0;
        for (; i < lengthList.size(); i++) {
            int num = lengthList.get(i).getSize();
            //按顺序累加
            groupNum += num;
            double curDiffSum = Math.abs(groupNum - average);

            int surplusGroupNum = m - 1 - pointArrIndex;
            int surplusDataNum = lengthList.size() - i;
            int differNum = surplusDataNum - surplusGroupNum;

            if (differNum > 0) {
                //当前累加 与平均值的距离 < 上次累加与平均值的距离
                if (curDiffSum < minDiffSum || minDiffSum == -1) {
                    minDiffSum = curDiffSum;
                } else {
                    //保存切分点
                    pointArr[pointArrIndex] = i;
                    if (pointArrIndex == m - 2) {
                        break;
                    }
                    pointArrIndex++;
                    groupNum = num;
                    minDiffSum = Math.abs(num - average);
                }
            } else {
                //简单解决大数分布到头尾，不够分组的情况。把末尾的每个值单独分为一组。
                pointArr[pointArrIndex++] = i;
                int point = i + 1;
                for (int j = 0; j < surplusGroupNum - 1; j++) {
                    pointArr[pointArrIndex++] = point++;
                }
                break;
            }

        }
        return pointArr;
    }
}
